//
//  filterTree.cpp
//  map-matching
//
//  Created by Lv Xin on 16/5/10.
//  Copyright © 2016年 Lv Xin. All rights reserved.
//
//  Personal Homepage: www.davidlvxin.com

#include "filterTree.h"
#include "distance.h"
#include "dijkstra.h"
#include "trajectory_generated.h"
#include "TR_SIM.h"

extern std::vector< std::vector<EdgeDis> > candidateEdge;
extern std::list<Route*> candidateR;
std::list<Route*> candidateRAfterTreeCut;

using namespace std;

RouteWithSima::RouteWithSima(Route* a){
    m = a;
    int TSize = candidateEdge.size();
    double dijSum = 0;
    for(int i = 0; i < TSize; i++){
        dijSum += candidateEdge[i][a->rank[i]].dis;
    }
    simA = 1 - dijSum / TSize;
}

TreeNode::TreeNode(int d, int r, TreeNode* p){
    deep = d, rank = r, parent = p;
    canUse = true; route = NULL;
    for(int i = 0; i < S; i++){
        child[i] = NULL;
    }
    if(p == NULL){
        lenthSoFar = 0;
    }else if(p->deep != -1){
        int inSize = candidateEdge[p -> deep][p -> rank].edge.size();
        double latLast = candidateEdge[p -> deep][p -> rank].edge[inSize - 1].endLat;
        double lngLast = candidateEdge[p -> deep][p -> rank].edge[inSize - 1].endLng;
        double latBegin = candidateEdge[deep][rank].edge[0].beginLat;
        double lngBegin = candidateEdge[deep][rank].edge[0].beginLng;
        lenthSoFar += distance2meter(latLast, lngLast, latBegin, lngBegin);
        int thisPointInSize = candidateEdge[deep][rank].edge.size();
        for(int i = 0; i < thisPointInSize; i++){
            lenthSoFar += distance2meter(candidateEdge[deep][rank].edge[i].beginLat, candidateEdge[deep][rank].edge[i].beginLng, candidateEdge[deep][rank].edge[i].endLat, candidateEdge[deep][rank].edge[i].endLng);
        }
    }else{
        int thisPointInSize = candidateEdge[deep][rank].edge.size();
        for(int i = 0; i < thisPointInSize; i++){
            lenthSoFar += distance2meter(candidateEdge[deep][rank].edge[i].beginLat, candidateEdge[deep][rank].edge[i].beginLng, candidateEdge[deep][rank].edge[i].endLat, candidateEdge[deep][rank].edge[i].endLng);
        }
    }
}

TreeNode::~TreeNode(){
    
}

FilterTree::FilterTree(Trajectary& T, Map* m) : traj(T){
    mapSet = m;
    list<Route*>::iterator s;
    for(s = candidateR.begin(); s != candidateR.end(); s++){
        RouteWithSima* temp = new RouteWithSima(*s);
        PQCandidate.push(temp);
    }
    root = new TreeNode(-1, 0, NULL);
    computeR1SimB();
    //需要算出R1的相似度第二部分
}

FilterTree::~FilterTree(){
    
}

void FilterTree::computeR1SimB(){
    Route* route = *(candidateR.begin());
    int size = candidateEdge.size();
    GenerateTrajectory temp;
    int firstSize = candidateEdge[0][route->rank[0]].edge.size();
    DoublePos post;
    PosWithRank r;
    post.lat = candidateEdge[0][route->rank[0]].edge[0].beginLat;
    post.lng = candidateEdge[0][route->rank[0]].edge[0].beginLng;
    r.pos = post;
    r.rank = candidateEdge[0][route->rank[0]].edge[0].begin;
    temp.point.push_back(r);
    for(int i = 0; i < firstSize; i++){
        DoublePos pos;PosWithRank r;
        pos.lat = candidateEdge[0][route->rank[0]].edge[i].endLat;
        pos.lng = candidateEdge[0][route->rank[0]].edge[i].endLng;
        r.pos = pos; r.rank = candidateEdge[0][route->rank[0]].edge[i].end;
        temp.point.push_back(r);
    }
    for(int i = 1; i < size; i++){
        if(temp.point[temp.point.size() - 1].pos.lat != candidateEdge[i][route->rank[i]].edge[0].beginLat || temp.point[temp.point.size() - 1].pos.lng != candidateEdge[i][route->rank[i]].edge[0].beginLng){//如果需要最短路
            vector<int> path;
            path.clear();
            path = findpath(temp.point[temp.point.size() - 1].rank, candidateEdge[i][route->rank[i]].edge[0].begin);
            int pathSize = path.size();
            for(int j = 0; j < pathSize; j++){
                DoublePos pp; PosWithRank rin;
                pp.lat = mapSet->node[path[j]].lat;
                pp.lng = mapSet->node[path[j]].lng;
                rin.pos = pp; rin.rank = mapSet->node[path[j]].rank;
                temp.point.push_back(rin);
            }
        }
        int RankSize = candidateEdge[i][route->rank[i]].edge.size();
        DoublePos postt;
        PosWithRank rr;
        postt.lat = candidateEdge[i][route->rank[i]].edge[0].beginLat;
        postt.lng = candidateEdge[i][route->rank[i]].edge[0].beginLng;
        rr.pos = post;
        rr.rank = candidateEdge[i][route->rank[i]].edge[0].begin;
        temp.point.push_back(rr);
        for(int j = 0; j < RankSize; j++){
            DoublePos poss;PosWithRank rs;
            poss.lat = candidateEdge[i][route->rank[i]].edge[j].endLat;
            poss.lng = candidateEdge[i][route->rank[i]].edge[j].endLng;
            rs.pos = poss; rs.rank = candidateEdge[i][route->rank[i]].edge[j].end;
            temp.point.push_back(rs);
        }
    }
    TR_SIM sim(temp, traj);
    sim.part2();
    R1SimB = sim.getSimPart2();
}

void FilterTree::outputToList(TreeNode* r){
    if(r -> deep == candidateEdge.size() - 1){
        candidateRAfterTreeCut.push_back(r -> route);
    }
    int size = candidateEdge[r -> deep].size();
    for(int i = 0; i < size; i++){
        outputToList(r -> child[i]);
    }
}

void FilterTree::deleteTreeNode(TreeNode* r){
    if(r -> deep == candidateEdge.size() - 1){
        delete r;
        return;
    }
    bool tmp = false;
    for(int i = 0; i < S; i++)
        if(r -> child[i] != NULL){
            tmp = true;
            break;
        }
    if(!tmp){
        delete r;
        return;
    }
    for(int i = 0; i < S; i++){
        if(r -> child[i] != NULL)
            deleteTreeNode(r -> child[i]);
    }
    delete r;
}

void FilterTree::insertNode(RouteWithSima* R){
    TreeNode* temp = root;
    int TSize = candidateEdge.size();
    for(int i = 0; i < TSize; i++){
        if(temp -> child[R->m->rank[i]] == NULL){
            TreeNode* c = new TreeNode(temp->deep + 1, R->m->rank[i], temp);
            temp -> child[R->m->rank[i]] = c;
            if(c -> lenthSoFar > traj.lenT && (1 - (c -> lenthSoFar - traj.lenT) / traj.lenT) < R1SimB){
                c -> canUse = false;
                break;
            }else{
                temp = c;
            }
        }else{
            temp = temp -> child[R->m->rank[i]];
            if(!temp -> canUse){
                break;
            }
        }
    }
    if(temp -> deep == candidateEdge.size() - 1){
        temp -> route = R -> m;
    }
}

void FilterTree::cutOff(){
    while(!PQCandidate.empty()){
        insertNode(PQCandidate.top());
        delete PQCandidate.top();
        PQCandidate.pop();
    }
    outputToList(root);
    deleteTreeNode(root);
}

std::string FilterTree::strategyName(){
    return "Tree";
}














